package main

import (
	"fmt"
	"runtime"
	"sync"
)

/*
----------希尔排序并发--------
前提：先理解希尔排序

思路：
1. 在希尔排序的基础上，因为希尔排序的每一组互不影响，所以可以并发排序每一组
 */
func main() {
	arr := []int{9,5,66,1,21,42}
	fmt.Println(shellSortGo(arr))
}

/*
和插入排序的 simpleInsert 函数一样，只不过步长不一样
*/
func simpleInsert(arr []int,idx int,gap int){
	// backup 为备份要向前插入的值，j 为前一个值
	backup,j := arr[idx],idx - gap

	for j >= 0 && arr[j] > backup{
		// 把值往后移动
		arr[j+gap] = arr[j]
		j = j - gap
	}

	// 把值放到合适的位置
	arr[j+gap] = backup
}

/*
和插入排序的 insertSort 函数一样，区别在插入排序的是整个数组，这个是插入排序一组

每一组进行插入排序
 */
func shellSortStep(arr []int, start int, gap int){
	// 循环每一组，插入排序是循环全部数组
	for i := start + gap;i < len(arr); i += gap {
		simpleInsert(arr,i,gap)
	}
}

func shellSortGo(arr []int) []int{
	if len(arr) <= 1 {
		return arr
	}

	// 获取逻辑cpu数量，并发数应该是这个的倍数
	cpuNum := runtime.NumCPU()
	wg := sync.WaitGroup{}

	for gap := len(arr)/2;gap > 0 ;gap /= 2  {
		wg.Add(cpuNum)
		ch := make(chan int,100)

		go func() {
			defer close(ch)

			// 每一组的开始值写进管道
			for i := 0; i < gap; i++ {
				ch <- i
			}
		}()

		for i := 0; i < cpuNum; i++ {
			go func() {
				defer wg.Done()

				for v := range ch{
					// 对每一组进行插入排序
					shellSortStep(arr,v,gap)
				}
			}()
		}

		wg.Wait()
	}

	return arr
}
